package com.lwx.leetcode.backtrack;

import java.util.*;

/**
 * 所有的排列
 */
public class Offer46 {
//    List<Boolean> visited;
//    List<List<Integer>> ret;
//    public List<List<Integer>> permute(int[] nums) {
//        ret = new ArrayList<>();
//        //第i个元素是否在当前的排列中
//        visited = new ArrayList<>(nums.length);
//        for (int i = 0; i < nums.length; i++) {
//            visited.set(i,false);
//        }
//        return ret;
//    }
//
//    /**
//     * p中为当前完成或未完成的排列
//     * @param nums
//     * @param p
//     */
//    public void generatePermutation(int[] nums, int index, Deque<Integer> p){
//        if(p.size() == nums.length){
//            ret.add(new ArrayList<>(p));
//            return;
//        }
//
//        if(!visited.get(index) && index < nums.length){
//            visited.set(index,true);
//            p.addLast(nums[index]);
//            generatePermutation(nums,index+1,p);
//            p.removeLast();
//            visited.set(index,false);
//        }
//
//    }

    List<List<Integer>> result;
    private List<Boolean> used;

    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        if(nums == null){
            return result;
        }
        used = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            used.add(i,false);
        }
        Deque<Integer> p = new ArrayDeque<>();
        generatePermutation(nums,0, p);
        return result;
    }

    /**
     * p中含有index个排列
     *
     */
    public void generatePermutation(int[] nums, int index, Deque<Integer> p){
        if(nums.length == p.size()){
            result.add(new ArrayList<>(p));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //如果没被使用过
            if(!used.get(i)){
                //是否nums[index]在p中
                p.addLast(nums[i]);
                used.set(i, true);
                generatePermutation(nums, i+1, p);
                p.removeLast();
                used.set(i, false);
            }
        }
        return;
    }

}
